#include <iostream>
using namespace std;
#include <stdlib.h>
#include <assert.h>
#include "LinkedList.h"

void LinkedList::InitList()
{
	list = NULL;
}

void LinkedList::ClearList()
{
	LinkedListNode* head = list;
	LinkedListNode * temp;
	while(head != NULL)
	{
		temp = head->next;
		delete head;
		head = temp;
	}
	list = NULL;
}

int LinkedList::GetListLength()
{
	LinkedListNode* head = list;
	int length = 0;
	for(;head!=NULL;head = head->next,length++);
		return length;
}
bool LinkedList::IsListEmpty()
{
	LinkedListNode* head = list;
	return (head == NULL);
}

int LinkedList::GetData(int pos)
{
	LinkedListNode* head = list;
	assert(pos>0&&head!=NULL);
	int count = 0;
	while(head!=NULL)
	{
		count++;
		if(count == pos)
		{
			return head->data;
		}
		head = head->next;
	}
	return -1;
}

void LinkedList::TranverseList()
{
	LinkedListNode* head = list;
	while(head !=NULL)
	{
		cout<<head->data<<" ";
		head = head->next;
	}
	cout<<endl;
}

LinkedListNode* LinkedList::FindLinkedListNodeInList(LinkedListNode*node)
{
	LinkedListNode* head = list;
	assert(node!=NULL);
	while(head!=NULL)
	{
		if(head->data == node->data)
			return head;
		head = head->next;
	}
	return NULL;
}

bool LinkedList::UpdateDataInList(int pos,LinkedListNode* node)
{
	LinkedListNode* head = list;
	assert(pos>0 && node!=NULL);
	int count = 0;
	while(head!=NULL)
	{
		count++;
		if(count == pos)
		{
			head->data= node->data;
			return true;
		}
		head = head->next;
	}
	return false;
}

void LinkedList::InsertListFirst(LinkedListNode*node)
{
	LinkedListNode* head = list;
	assert(node!=NULL);
	LinkedListNode* newLinkedListNode = new LinkedListNode();
	assert(newLinkedListNode!=NULL);
	newLinkedListNode->data = node->data;
	newLinkedListNode->next = NULL;
	if(head== NULL)
		head = newLinkedListNode;
	else
	{
		newLinkedListNode->next = head;
		head = newLinkedListNode;
	}
	list = head;
}

void LinkedList::InsertListLast(LinkedListNode*node)
{
	LinkedListNode* head = list;
	assert(node!=NULL);
	LinkedListNode *newLinkedListNode = new LinkedListNode();
	assert(newLinkedListNode!=NULL);
	newLinkedListNode->data = node->data;
	newLinkedListNode->next = NULL;
	if(head == NULL)
		list = newLinkedListNode;
	else
	{
		LinkedListNode* prenode = head;
		while(head!=NULL)
		{
			prenode = head;
			head = head->next;
		}
		prenode->next = newLinkedListNode;
	}
}

bool LinkedList::InsertListPos(int pos,LinkedListNode* node)
{
	LinkedListNode* head = list;
	assert(node!=NULL && pos>0);
	int count = 0;
	LinkedListNode *prenode = NULL;
	if(pos == 1)
	{
		InsertListFirst(node);
		return true;
	}
	else
	{
		while(head!=NULL)
		{
			count++;
			if(count == pos)
			{
				LinkedListNode *newLinkedListNode = new LinkedListNode();
				newLinkedListNode->data = node->data;
				newLinkedListNode->next = head;
				prenode->next = newLinkedListNode;
				return true;
			}
			prenode = head;
			head = head->next;
		}
		return false;
	}
}

void LinkedList::InsertOrderList(LinkedListNode* node)
{
	LinkedListNode* head = list;
	assert(node != NULL);
	if(head== NULL || head->data>node->data)
	{
		InsertListFirst(node);
	}
	else
	{
		LinkedListNode *prenode = NULL;
		LinkedListNode *newLinkedListNode = new LinkedListNode(node->data);
		assert(newLinkedListNode!=NULL);
		while(head!=NULL)
		{
			if(head->data >node->data)
			{
				break;
			}
			prenode = head;
			head = head->next;
		}
		prenode->next = newLinkedListNode;
		newLinkedListNode->next = head;
	}
}

int LinkedList::DeleteListFirst()
{
	LinkedListNode* head = list;
	assert(head!=NULL);
	LinkedListNode *node = head;
	head = head->next;
	int result = node->data;
	delete node;
	list = head;
	return result;
}

int LinkedList::DeleteListLast()
{
	LinkedListNode* head = list;
	assert(head!=NULL);
	int result = head->data;
	if(head->next == NULL)
	{
		delete head;
		list = NULL;
		return result;
	}
	else
	{
		LinkedListNode *prenode = NULL;
		LinkedListNode *curLinkedListNode = head;
		while(curLinkedListNode->next != NULL)
		{
			prenode = curLinkedListNode;
			curLinkedListNode = curLinkedListNode->next;

		}
		result = curLinkedListNode->data;
		prenode->next = NULL;
		delete curLinkedListNode;
		return result;
	}

}

int LinkedList::DeleteListPos(int pos)
{
	LinkedListNode* head = list;
	assert(pos>0);
	LinkedListNode *preLinkedListNode = NULL,*curLinkedListNode = head;
	if(head == NULL)
	{
		exit(-1);
	}
	else if(head->next == NULL)
	{
		if(pos == 1)
			return DeleteListFirst();
		else
			exit(-1);
	}
	else if(pos == 1)
		return DeleteListFirst();
	else
	{
		int count = 0;
		while(curLinkedListNode->next!=NULL)
		{
			count++;
			if(count == pos)
				break;
			preLinkedListNode = curLinkedListNode;
			curLinkedListNode = curLinkedListNode->next;
		}
		if(count == pos || count==(pos-1))
		{
			int result = curLinkedListNode->data;
			preLinkedListNode->next = curLinkedListNode->next;
			delete curLinkedListNode;
			return result;
		}
		else
		{
			exit(-1);
		}
	}

}

bool LinkedList::DeleteListValue(LinkedListNode *node)
{
	LinkedListNode* head = list;
	assert(node!=NULL);
	LinkedListNode*  preLinkedListNode = NULL,*curLinkedListNode = head;
	if(curLinkedListNode== NULL)
		return false;
	else if(curLinkedListNode->next == NULL)
	{
		if(curLinkedListNode->data == node->data)
		{
			DeleteListFirst();
			return true;
		}
		else
		{
			return false;
		}
	}
	else if(curLinkedListNode->data == node->data)
	{
		DeleteListFirst();
		return true;
	}
	else
	{
		while(curLinkedListNode->next != NULL)
		{
			if(curLinkedListNode->data == node->data)
			{
				preLinkedListNode->next = curLinkedListNode->next;
				delete curLinkedListNode;
				return true;
			}
			preLinkedListNode = curLinkedListNode;
			curLinkedListNode = curLinkedListNode->next;
		}
		if(curLinkedListNode->data == node->data)
		{
			preLinkedListNode->next = NULL;
			delete curLinkedListNode;
			return true;
		}
		else
			return false;
	}
}
